This invention relates to systems and methods for searching a state space, i.e., a set of a plurality of states or combinations, and more particularly to methods of solving combinatorial optimization problems by which the optimal combination is discovered from among the possible combinations.
FIG. 1 is a flowchart showing a conventional breadth-first search algorithm for searching a state space, which is discussed in: Nils J. Nilsson, "Problem Solving Methods in Artificial Intelligence", Mcgraw-Hill Publications, New York, 1971. The state space is searched using two lists, OPEN and CLOSED, which hold the nodes of the state space whose neighbors are going be examined and those whose neighboring nodes have already been examined, respectively. After initialization, these two lists, OPEN and CLOSED, are successively updated to find out the goal node.
Thus at step S11, the list OPEN is initialized to hold a start state S. Further, the list CLOSED is initialized to null (i.e., a list having no elements). Next, at step S12, it is judged whether or not the list OPEN is null. When the list OPEN becomes null at step S12, the search fails. As long as there remains nodes in OPEN, the search continues. At step S13, the first node is taken out from the list OPEN, put in the list CLOSED, and named as node n. At step S14, extension or continuation nodes of node n, namely, the neighbors of node n (the nodes to which a direct transition from node n is possible) which are not contained in either OPEN or CLOSED, are appended after the tail of the list OPEN. Further, the pointer to node n is stored such that the fact that these nodes result from transitions from the node n is stored. At step S15, it is judged whether or not a goal node exists among the extension nodes, which have been added to the tail of list OPEN. If there is, the search succeeds. If not, the execution returns to step S12 and the search is continued until either success or failure of the search is determined.
As described above, the node or state at the head of the list OPEN is taken out as the current state (step S13), and then the neighboring states of the current state which have not yet been examined are added to the list OPEN (step S14). Finally, either success or failure of search is determined at step S15 or step S12.
The above conventional state space search method, however, has the following disadvantage. Since all the unexamined neighboring states of the current state or node n are added to the list OPEN, the requirement for the storage capacity for the list OPEN becomes enormous. Further, since the search is uninformed, the efficiency of the search is low. Thus, it has already been proposed to evaluate the states added to the list OPEN by means of an evaluation function. Then, however, the discovery of the optimum solution is not guaranteed.